package com.example.hot100;

import java.util.Arrays;

/**
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 *
 *  示例:
 *  输入: [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 */
public class Leetcode283_MoveZeroes {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 12};
        new Solution().moveZeroes(nums);
        System.out.println(Arrays.toString(nums));
    }

    static class Solution {
        /**
         * 解法二:直接覆盖
         * 首先遍历整个数组，将不是0的数据依次覆盖掉原来位置的值(这样可以保证非零的数据顺序不变)
         * 然后将后面段的所有数据置为0即可
         * @param nums
         */
        public void moveZeroes2(int[] nums) {
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] != 0) {
                    nums[count++] = nums[i];
                }
//                System.out.println(Arrays.toString(nums));
            }

            while (count < nums.length) {
                nums[count++] = 0;
            }
        }

        /**
         * 解法一:双指针
         * @param nums
         */
        public void moveZeroes1(int[] nums) {
            if (nums == null ||nums.length == 0) return;
            int left = 0, right = 0; // left指向已经处理的尾部, right 指向已经待处理的序列头部 左指针左边均为非零数；右指针左边直到左指针处均为零
            while (right < nums.length) {
                if (nums[right] != 0) {
                    int tmp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = tmp;
                    ++left;
                }

//                System.out.println(Arrays.toString(nums));

                right++;
            }
        }

        public void moveZeroes(int[] nums) {
            moveZeroes2(nums);
        }
    }
}
